package stu.day25_day32.day31;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

public class hw5 {
    HashMap<Integer, Set<Integer>> map1 = new HashMap<>();
    HashMap<Integer,Set<Integer>> map2 = new HashMap<>();
    HashMap<Integer,Set<Integer>> map3 = new HashMap<>();

    char[][] ch = new char[9][9];
    public void solveSudoku(char[][] board) {

        for(int i=0;i<board.length;i++){
            Set<Integer> s1 = new HashSet<>();
            for(int j=0;j<board[0].length;j++){
                if(board[i][j]!='.'){
                    s1.add((int)board[i][j]);
                }
                map1.put(i,s1);
            }
        }

        for(int i=0;i<board[0].length;i++){
            Set<Integer> s2 = new HashSet<>();
            for(int j=0;j<board.length;j++){
                if(board[j][i]!='.'){
                    s2.add((int)board[i][j]);
                }
                map2.put(i,s2);
            }
        }

        int num = 0;
        for(int i=0;i<board.length; i+=3){
            for(int j=0;j<board[0].length; j+=3){
                Set<Integer> s3 = new HashSet<>();

                for(int p=i;p<i+3;p++){
                    for (int q=j;q<j+3;q++){
                        if(board[j][i]!='.'){
                            s3.add((int)board[i][j]);
                        }
                    }
                }
                map3.put(num,s3);
                num +=1;
            }
        }

        backtrack(0,0,board,0);
        System.arraycopy(ch, 0, board, 0, 9);

    }



    public void backtrack(int i,int j,char[][] board,int num){
        if(i==9){
            for (int x = 0; x < 9; x++) {
                ch[x] = board[x].clone();
            }
            return;
        }


        if(board[i][j]=='.'){
            int xx = (i/3)*3+j/3;
            if(!map1.get(i).contains(num) && !map2.get(j).contains(num) && !map3.get(xx).contains(num)){
                map1.get(i).add(num);
                map2.get(i).add(num);
                map3.get(i).add(num);
                board[i][j] = Character.forDigit(num,10);
                for(int k=1;k<board.length+1;k++){
                    if((j+1)>=board.length){
                        backtrack(i+1,j,board,k);
                    }else {
                        backtrack(i,j+1,board,k);
                    }
                }
                board[i][j] = '.';
                map1.get(i).remove(num);
                map2.get(i).remove(num);
                map3.get(i).remove(num);

            }
        }else {
            for(int k=1;k<board.length+1;k++){
                if((j+1)>=board.length){
                    backtrack(i+1,j,board,k);
                }else {
                    backtrack(i,j+1,board,k);
                }
            }
        }
    }
}
